/* Authors:
 * Igor Rafael [igor@dcc.ufmg.br]
 * Pericles Alves [periclesrafael@dcc.ufmg.br]
 *
 */

#include "Ion.h"
#include "IonSpewer.h"
#include "CP.h"
#include "MIR.h"
#include "MIRGraph.h"

using namespace js;
using namespace js::ion;
using namespace js::ion::cp;

CP::CP(MIRGraph &graph)
  : graph(graph)
{
#ifdef DEBUG
    actualScript = NULL;
    numFolded = 0;
    failsDueToType = 0;
    totalInst = 0;
#endif
}

#ifdef DEBUG
#define PERCENT(n,d) (d==0 ? 0 : n/d),(d == 0 || n == d ? 0 : (int)(100*((double)n)/d))
inline void CP::printStats(){
    JS_ASSERT(actualScript != NULL);
    IonSpew(IonSpew_PassStats, "%d [%d.%d] instructions successfully propagated.", numFolded, totalInst, PERCENT(numFolded,totalInst));
    IonSpew(IonSpew_PassStats, "%d [%d.%d] propagation fails due to unsupported types.", failsDueToType, PERCENT(failsDueToType,totalInst));
    SAVE_STATS(actualScript,numFolded,totalInst);
}

IonSpewChannel 
CP::getIonSpewChannel()
{
    return IonSpew_CP;
}
#endif

bool 
CP::initWorkList()
{
    //Default implementation: Adds uses of constant instructions in the graph to the work list
    for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
        for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); phi++)
            countInst();

        for (MInstructionIterator instIt(block->begin()); instIt != block->end(); instIt++) {
            countInst();
        
            MInstruction *instruction = *instIt;

            if (instruction->isConstant() && isPropagableValue(&(instruction->toConstant()->value()))) {
                addUsesToWorkList(instruction);
            }
        }
    }

    return true;
}

bool
CP::analyze()
{
    IonSpew(getIonSpewChannel(), "Beginning optimization pass.");
    if(!initWorkList())
        return false;

    //Definitions are propagated until there are no more phi cycles to be solved
    do {
        std::set<MPhi*> phiWorkList;
        while (!workList.empty()) {
            //Gets a new element from the work list
            MDefinition *def = *(workList.begin());
            workList.erase(workList.begin());

            //FIXME: We must be able to fold test instructions
            if (def->isTest())
                continue;

            MDefinition *foldResult = def->foldsToConstant();

            //Propagates a folded definition
            if ((foldResult != def) && (foldResult->isInstruction())) {
                MInstruction *resultInstruction = foldResult->toInstruction();

                IonSpew(getIonSpewChannel(), "Definition %d folded.", def->id());

                //Uses may be constant propagable too
                addUsesToWorkList(def);
                def->replaceWithInstruction(resultInstruction);
                countNumFolded();
                
                if(def->isPhi())
                    phiWorkList.erase((MPhi*)def);              

            //A non-propagated phi could be part of a phi cycle
            } else if (def->isPhi()) {
                phiWorkList.insert((MPhi*)def);
            }
        }

        solvePhiCycles(phiWorkList);
    } while (!workList.empty());

    printStats();
    return true;
}

void 
CP::addUsesToWorkList(MDefinition *def)
{
    for (MUseIterator useIt(def->usesBegin()); useIt != def->usesEnd(); useIt++) {
        MUse *use = *useIt;
        
        if (use->node()->isDefinition()) {
            workList.insert((MDefinition *)use->node());
        }
    } 
}

void
CP::solvePhiCycles(std::set<MPhi*> &workList)
{
    std::map<MPhi*, cp::PhiItem> phiMap;

    //try to propagate the state of phi's along the chain
    while(!workList.empty()){
        MPhi* phi = *(workList.begin());
        workList.erase(workList.begin());

        //insert/get from phiMap
        std::pair<std::map<MPhi*, PhiItem>::iterator, bool>
            phiInMap = phiMap.insert(std::make_pair(phi, PhiItem()));
        PhiItem & pi = phiInMap.first->second;

        bool updated = false;
        //propagate state from phi operands
        for (size_t i = 0; i < phi->numOperands(); ++i) {
            MDefinition* operand = phi->getOperand(i);
            if (operand->isConstant()) {
                PhiItem opr = PhiItem(Constant,(MConstant*)operand);
                updated |= propagate(pi, opr);
            } else if(operand->isPhi()) {
                std::pair<std::map<MPhi*, PhiItem>::iterator, bool>
                    phiOperandInMap = phiMap.insert(std::make_pair(phi, PhiItem()));
                PhiItem & piOperand = phiOperandInMap.first->second;
                updated |= propagate(pi, piOperand);
            }else {
            	PhiItem opr = PhiItem(Top, NULL);
            	updated |= propagate(pi, opr);
            }
        }
        
        if (updated && pi.s != Top) {
            workList.insert(phi);
        }
    }

    //only for debug
    int b = 0, c = 0, t = 0;

    for (std::map<MPhi*, cp::PhiItem>::iterator bgn = phiMap.begin(), end = phiMap.end(); bgn != end; ++bgn) {
        MPhi *phi = bgn->first;
        PhiItem *pi = &(bgn->second);
        if (pi->s == Constant) {
            JS_ASSERT(pi->c != NULL);
            for (size_t i = 0; i < phi->numOperands(); ++i) {
                phi->replaceOperand(i,pi->c);
            }
            this->workList.insert(phi);
        }
        ANALYSE_STATE(pi->s,b,c,t);
    }

    IonSpew(getIonSpewChannel(), "\tPhi Cycles [Bottom,Constant,Top] = [%d,%d,%d]", b, c, t);
}

bool 
CP::propagate(cp::PhiItem &to, cp::PhiItem &from)
{
    switch (to.s) {
      case Bottom:
        to = from;
        if(from.s != Bottom) return true;
        break;
      case Constant:
        JS_ASSERT(to.c != NULL);
        if(from.s == Top ||
          (from.s == Constant && from.c->value() != to.c->value()))
        {
            to.s = Top;
            to.c = NULL;
            return true;
        }
        break;
      case Top:
        break;
    }
    return false;
}
